package org.ala.linshen.dp;

import java.util.*;

/**
 * 一个魔法师有许多不同的咒语。
 *
 * 给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。
 *
 * 已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。
 *
 * 每个咒语最多只能被使用 一次 。
 *
 * 请你返回这个魔法师可以达到的伤害值之和的 最大值 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：power = [1,1,3,4]
 *
 * 输出：6
 *
 * 解释：
 *
 * 可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。
 *
 * 示例 2：
 *
 * 输入：power = [7,1,6,6]
 *
 * 输出：13
 *
 * 解释：
 *
 * 可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。
 *
 *
 *
 * 提示：
 *
 * 1 <= power.length <= 105
 * 1 <= power[i] <= 109
 *
 * @author ala
 * @data 2024-09-14 10:10
 */
public class Q3186 {

    public static void main(String[] args) {
        Q3186 q = new Q3186();

        int[] power = {1, 1, 3, 4};
//        int[] power = {7,1,6,6};
//        int[] power = {5,1,4};
//        int[] power = {1,1,1,1,1,1};
//        int[] power = {2,1,2,3,2,2,1,2};
//        int[] power = {7,1,6,3};
//        int[] power = {5,9,2,10,2,7,10,9,3,8};

        System.out.println(q.maximumTotalDamage(power));
    }

    public long maximumTotalDamage(int[] power) {
        return V1(power);
    }
    /**
     *  dp[i]表示前i个咒语（不含i），组合的最大伤害
     */
    protected long V1(int[] power) {
        Map<Integer, Integer> cnts = new HashMap<>();
        for (int p : power) {
            cnts.merge(p, 1, Integer::sum);
        }

        int[] nums = cnts.keySet().stream().sorted((i1, i2) -> i1 - i2).mapToInt(i -> i.intValue()).toArray();

        long[] dp = new long[nums.length + 1];
        int j = 0;
        for (int i = 0 ; i < nums.length ; i++) {
            int v = nums[i];
            while (nums[j] < v - 2) { j++; }
            dp[i + 1] = Math.max(dp[i], dp[j] + (long)v * cnts.get(v));
        }
        return dp[nums.length];
    }
}
